#include "kmeans.h"
#include <math.h>

/** ********************************************************************
 **         KMEANS
 ** ********************************************************************
 ** Version by:
 **		Marcelo Barros de Almeida - barros@cpdee.ufmg.br
 **     http://www.cpdee.ufmg.br/~barros/
 **
 ** History:
 ** --------------------------------------------------------------------
 ** Date/Ver  Author  Description                                              
 ** --------------------------------------------------------------------
 ** 08/Fev/02 Bernardo Penna Resende de Carvalho
 ** V2.00b    Second version.  Stopping criteria included. 
 **           Feature extraction and feature selection for 
 **           distance calculation included.
 ** --------------------------------------------------------------------
 ** 16/Jun/00 Marcelo Barros de Almeida
 ** V1.00b    First version.
 **					
 ** ********************************************************************/
 
/** ********************************************************************
 ** TODO LIST
 ** =========
 ** 1)
 ** *******************************************************************/


heap::heap(int sz){
  size = sz;
  count = 0;
  itens = new heapItem [size];
}

heap::~heap(){
  delete itens;
}

void heap::add(float val, int idx) {
 
  itens[count].value = val;
  itens[count].index = idx;
     
  if(count == 0) {
    count++;
    return;
  }
		      
  int place = count;
  int parent = (int)((place-1)/2);
  heapItem hi;
			    
  while((parent >= 0)&&(itens[place].value > itens[parent].value)) {
    hi = itens[parent];
    itens[parent] = itens[place];
    itens[place] = hi;
    place = parent;
    parent = (int)((place-1)/2);
  }
											       
  count++;
												 
}

int heap::remove(int idx) {
  if(count == 0) 
    return -1;
		  
  heapItem hi = itens[idx];
  count--;
  itens[idx] = itens[count];
  rebuild(idx);
			  
  return hi.index;
			    
}

void heap::rebuild(int idx) {
 
  int child = 2*idx + 1;
   
  if(child < count) {
 
    int rchild = child + 1;
   
    if((rchild < count)&&(itens[rchild].value > itens[child].value))
      child = rchild;
								     
    if(itens[idx].value < itens[child].value) {
      heapItem hi = itens[idx];
      itens[idx] = itens[child];
      itens[child] = hi;
      rebuild(child);
    }
														 
  }
}
  
/** *******************************************************************
 ** findCenters
 ** *******************************************************************/
INT Kmeans::findClusters(){
 
  INT i, j, k, moved;
  numIter = 0;
  CHAR str[80];
  INT MAX_ITER_TO_SAVE = 150;
	 
  if((calcDim) && (value)){
    cout << "Error: wrong dimensionality reduction requested, "
      "use just one method: selection or extraction." << endl << flush;
    exit(0);
  }
				   
  //vectors to save information about iterations
  for (i = 0; i < MAX_ITER_TO_SAVE; i++){
    swapIter.push_back(0);
    timeIter.push_back(0);
    calcDistIter.push_back(0);
  }
  
  // initialize random seed
  SRAND(time(NULL));

  // start to count time
  crono.startCronometer();
  crono2.startCronometer();

  // initialize data
  printMsg((CHAR*)"Initializing cluster centers...\n",GENERAL_MSGS);

  if(stop == 0){
    initCentersRandom(); // cria clusters aleatorios na partida
	  crono.finishCronometer();
	  crono2.finishCronometer();
		timeIter[0] = crono2.getElapsedTime();
		return TRUE;
	}
  else
    initCenters();
	
  crono2.finishCronometer();
  timeIter[0] = crono2.getElapsedTime();
  
  // man loop
  printMsg((CHAR*)"Initializing main loop...\n",GENERAL_MSGS);
  int loop=TRUE;
  if (stop!=numIter){
    while(loop){
      crono2.startCronometer();
      moved = 0;
      // STEP 1:  calculate necessaries distances
			for(i = 0 ; i < numClusters ; i++){
				if(centerChanged[i]){
					calcDistIter[numIter+1]++;
					for(j = 0 ; j < numExamples; j++){
						if(calcDim || value)
							distance[i][j] = calcDist(tmpCenter[i],tmpPoint[j]);
						else
							distance[i][j] = calcDist(center[i],point[j]);
					}
				}		
			}

      // STEP 2: compute membership
      for(i = 0 ; i < numExamples; i++){
				INT min = 0;
				for(j = 0 ; j < numClusters ; j++){ //j starts from 0 or 1 ? 
					if(distance[j][i] < distance[min][i])
						min = j;
				}
				if(membership[i] != min){
					moved++;
					membership[i] = min;
				}
			}

			// STEP 3: Update cluster centers
			// If feature extraction or selection ....
      if (calcDim || value){
				for(i = 0 ; i < numClusters ; i++){
					numPointsInCluster[i] = 0;
					REAL_VECTOR vtmp2(dimReduced,0);
					for(j = 0 ; j < numExamples; j++){
						if(membership[j] == i){
							for(k = 0 ; k < dimReduced; k++)
								vtmp2[k] += tmpPoint[j][k];			
							++numPointsInCluster[i];
						}
					}
 
				  INT change = FALSE;
					REAL_VECTOR oldTmpCenter(tmpCenter[i]);
			     
					if(numPointsInCluster[i]){
						for(k = 0 ; k < dimReduced; k++)
							tmpCenter[i][k] = vtmp2[k]/numPointsInCluster[i];	          
					}
					else {
						cout << "Cluster " << i << " empty at round " << numIter  << endl << flush;
					}
								
					if(isSameVector(oldTmpCenter,tmpCenter[i]))
						centerChanged[i] = FALSE;
					else
						centerChanged[i] = TRUE;
				}
      } // ... or if traditional approacho without dimensionality reduction
      else{
				for(i = 0 ; i < numClusters ; i++){
					numPointsInCluster[i] = 0;
					REAL_VECTOR vtmp(dim,0);
					for(j = 0 ; j < numExamples; j++){
						if(membership[j] == i){
							for(k = 0 ; k < dim; k++)
								vtmp[k] += point[j][k];			
							++numPointsInCluster[i];
						}
					}
					//INT change = FALSE;
					REAL_VECTOR oldCenter(center[i]);
			     
				  // ------------
					if(numPointsInCluster[i]){
						for(k = 0 ; k < dim; k++){
							center[i][k] = vtmp[k]/numPointsInCluster[i];
						}
					}
					else {
						cout << "Cluster " << i << " empty at round " << numIter  << endl << flush;
					}					

					if(isSameVector(oldCenter,center[i]))
						centerChanged[i] = FALSE;
					else
						centerChanged[i] = TRUE;
				}
      }

      cout <<"Iteration = " << ++numIter << "\tMoved = " << moved << endl << flush;
      printMsg(str,GENERAL_MSGS);
      crono2.finishCronometer();
      timeIter[numIter]=crono2.getElapsedTime();
      swapIter[numIter]=moved;
      // STEP 4: test convergence with stopping criteria
      if((!moved)||(stop==numIter))
	loop=FALSE;
    }
  }
 									 
  swapIter[0]=numIter;
  // finish time counter
  crono.finishCronometer();	
  return TRUE;
  
}

/**********************************************************************

** printHelp

**********************************************************************/

VOID Kmeans::printHelp(CHAR* argv){
  
 
 
  cout << "Usage:\n\n" << argv << " -option1 value1 -option2 value2 ...\n\n";
 
  cout << "Options (all in lower case !):\n\n";
 
  cout << 
   
    "Number of clusters:\n"
   
    "-nc value\n\n"
   
    "Number of iterations to perform:\n"
   
    "-stop value\n\n"
   
    "Membership initialization method:\n"
   
    "-init value\n\n"
   
    "When using high dimension data, it is possible\n"
   
    "to use one of these methods:\n"
   
    "Feature extraction OR Feature selection\n\n"	  
   
    "Number of dimensions to compute distances:\n"
   
    "-extraction value\n\n"
   
    "Minimum value of occurencies at each dimension\n"
   
    "to be used at distance calculations:\n"
   
    "-selection value\n\n"
   
    "Detailed information file:\n"
   
    "-detail filename\n\n"
   
    "Data file. This first two numbers must specify the\n"
   
    "number of points and the dimension of the input vector.\n"
   
    "After this two values, other points are considered as data,\n"
   
    "one data vector per row with targets at last colunm.\n"
   
    "The targets are not used at kmeans, but the input file\n" 
   
    "must have them.\n"
   
    "-i filename\n\n"
   
    "Output file:\n"
   
    "-o filename\n\n"
   
    "Verbosity level:\n"
   
    "-v level\n\n"
   
    "Help:\n"
   
    "-h\n" << endl << flush;
 
}

/**********************************************************************

** loadParams

**********************************************************************/

INT Kmeans::loadParams(INT argn, CHAR** argv){
  
 
 
  verbLevel = 0;
 
   
 
  if(!checkLineArg(argn,argv)){
   
    return FALSE;
 
  }
 
  if(!loadData()){
   
    return FALSE;
 
  }	
 
  return TRUE;
 
}



/**********************************************************************

** checkLineArg

**********************************************************************/

// treat command line arguments

INT Kmeans::checkLineArg(INT argn, CHAR** argv){
  
 
 
  INT i;
 
   
 
  //default values
  stop = -1;
  init = 0;
  value  = 0; 
  calcDim = 0;
  dimReduced = 0; 
	   
   
  if(argn<6){
     
    printHelp(argv[0]);
 
    return FALSE;
 
  }
   
		       
   
  for(i = 1 ; i < argn; i++){
     
    if(strcmp(argv[i],"-nc")==0){
   
      numClusters = (INT) atoi(argv[++i]);
 
    }
 
    else if(strcmp(argv[i],"-stop")==0){
   
      stop = (INT) atoi(argv[++i]);
 
    }
 
    else if(strcmp(argv[i],"-extraction")==0){
   
      calcDim = (INT) atoi(argv[++i]);
 
    }
 
    else if(strcmp(argv[i],"-selection")==0){
   
      value = (INT) atoi(argv[++i]);
 
    }
 
    else if(strcmp(argv[i],"-init")==0){
   
      init = (INT) atoi(argv[++i]);
 
    }
 
    else if(strcmp(argv[i],"-i")==0){
   
      strcpy(inFile,argv[++i]);
 
    }
 
    else if(strcmp(argv[i],"-o")==0){
   
      strcpy(outFile,argv[++i]);
 
    }
 
    else if(strcmp(argv[i],"-detail")==0){
   
      strcpy(detailFile,argv[++i]);
 
    }
 
    else if(strcmp(argv[i],"-v")==0){
   
      verbLevel = atoi(argv[++i]);
 
    }
 
    else if(strcmp(argv[i],"-h")==0){
   
      printHelp(argv[0]);
 
      return FALSE;
 
    }
 
  }
   
						   
   
  return TRUE;
   
}

/**********************************************************************

** loadData

**********************************************************************/

INT Kmeans::loadData(){
  
 
 
 
 
  INT i, j;
 
  REAL_NUMBER tmp;
 
     
 
  ifstream file(inFile);
 
       
 
  if (!file) {
   
    cerr << "Error when opening " << inFile << endl;
 
    return FALSE;
 
  }
 
		    
 
		    
 
  file >> numExamples;
 
  file >> dim;
 
			
 
  for (i = 0; i < numExamples; i++) {
   
    vector<REAL_NUMBER> vtmp;
 
    for (j = 0; j < dim; j++) {
   
      file >> tmp;
 
      vtmp.push_back(tmp);
 
    }
 
    point.push_back(vtmp);
 
    file >> tmp;
 
    target.push_back(tmp);
 
  }
 
							    
 
  file.close();
 
  return TRUE;
 
								
 
}

/**********************************************************************

** printSummary

**********************************************************************/

INT Kmeans::printSummary(){
  
 
 
  cout << "# Kmeans result:\n"
   
    "# ==============\n";
 
  cout << "# Number of centers = " << numClusters << endl;		
 
  //cout << "# Number of iterations:" << swapIter[0] << endl; 
 
  cout << "# Training time (CPU seconds): " << crono.getElapsedTime() << endl;		
 
  if (calcDim)
   
    cout << "# Number of dimension for feature extraction:" << calcDim << endl;
 
  if (value)
   
    cout << "# Value used for feature selection:" << value << endl;
 
  return TRUE;

	cout << flush;
 
}

/**********************************************************************

** saveResult

**********************************************************************/
INT	Kmeans::saveResult()
{
  UINT i, j, k;
  ofstream file(outFile);
     
  if(!file){
    cout << "Error opening " << outFile << endl << flush;
    exit(1);
  }
		
	// if extraction or selection, recalculate centers:
	if(calcDim || value){
		for(i = 0 ; i < numClusters ; i++){
			numPointsInCluster[i] = 0;
			REAL_VECTOR vtmp(dim,0);
			for(j = 0 ; j < numExamples; j++){
				if(membership[j] == i){
					for(k = 0 ; k < dim; k++)
						vtmp[k] += point[j][k];			
					++numPointsInCluster[i];
				}
			}
			if(numPointsInCluster[i]){
				for(k = 0 ; k < dim; k++){
					center[i][k] = vtmp[k]/numPointsInCluster[i];
				}
			}
			else {
				cout << "[Print]Cluster " << i << " empty at round " << numIter  << endl << flush;
			}
		}
	}

  // line with "#" as first character are comments
  file << "###### Kmeans file version" << endl;
  file << CURRENT_KMEANS_VERSION << endl;
		    
  file << "###### CPU time" << endl;
  //file.setiosflags(ios::flags|ios::scientific);setiosflags( ios::scientific )
  file << crono.getElapsedTime() << endl;	
			
  file << "###### Number of clusters" << endl;
  file << numClusters << endl;
			    
  file << "###### vector dimension " << endl;
  file << dim << endl;		
				
  file << "###### centers - one per line" << endl;
  for(i = 0 ; i < numClusters ; i++){
    for(j = 0 ; j < dim ; j++)
      file << center[i][j] << " ";	
    file << endl;
  }
								      
  file << "###### membership - one per line" << endl;
  for(i = 0 ; i < numExamples ; i++)
    file << membership[i] << endl;	
													    
  file << "###### points per cluster" << endl;
  for(i = 0 ; i < numClusters ; i++)
    file << numPointsInCluster[i] << endl;	
																		  
																		  
  file.close();
																		    
  return TRUE;
}

INT	Kmeans::saveResult2()
  
{
  
  INT i, j, k;
  ofstream file(outFile);
      
  if(!file){
   
    cout << "Error opening " << outFile << endl << flush;
 
    exit(1);
 
  }
 
		
 
  for(i = 0 ; i < numClusters ; i++){
   
    numPointsInCluster[i] = 0;
 
    REAL_VECTOR vtmp(dim,0);
 
    for(j = 0 ; j < numExamples; j++){
   
      if(membership[j] == i){
   
	for(k = 0 ; k < dim; k++)
   
	  vtmp[k] += point[j][k];			
 
	++numPointsInCluster[i];
 
      }
 
    }
 
    for(k = 0 ; k < dim; k++)
   
      center[i][k] = vtmp[k]/numPointsInCluster[i];
 
  }
 
  cout << "Saving result file..."<< endl << flush;
 
  // line with "#" as first character are comments
 
  file << "###### Kmeans file version" << endl;
 
  file << CURRENT_KMEANS_VERSION << endl;
 
							  
 
  file << "###### CPU time" << endl;
 
  //file.setiosflags(ios::flags|ios::scientific);setiosflags( ios::scientific )
 
  file <<	crono.getElapsedTime() << endl;	
 
							      
 
  int num =0;
 
  for (i=0;i<numClusters;i++)
   
    if (numPointsInCluster[i])
       
      num++;
 
											     
 
  file << "###### Number of clusters" << endl;
 
  //file << numClusters << endl;
 
  file << num << endl;
 
												 
 
  file << "###### vector dimension " << endl;
 
  file << dim << endl;		
 
												     
 
  file << "###### centers - one per line" << endl;
 
  for(i = 0 ; i < numClusters ; i++){
   
    if (numPointsInCluster[i]){	
   
      for(j = 0 ; j < dim ; j++)
   
	file << center[i][j] << " ";	
 
      file << endl;
 
    }
 
  }
 
																	   
 
  file << "###### membership - one per line" << endl;
 
  //for(i = 0 ; i < numExamples ; i++)
 
  //		file << membership[i] << endl;	
 
																	     
 
  num=0;
 
  for (i=0;i<numClusters;i++){
   
    if (numPointsInCluster[i])
   
      offsetMembership[i]=num;
 
    else 
   
      num++;
 
  }
 
																					    
 
  for (i=0;i<numExamples;i++)
   
    file<<membership[i] - offsetMembership[membership[i]]<<endl;
 
																									 
 
  file << "###### points per cluster" << endl;
 
  for(i = 0 ; i < numClusters ; i++)
   
    if (numPointsInCluster[i])	
       
      file << numPointsInCluster[i] << endl;	
 
																													       
 
																													       
 
  file.close();
 
																														 
 
  return TRUE;
 
}

/**********************************************************************

** saveDetail

**********************************************************************/

INT	Kmeans::saveDetail()
  
{
  
  INT i;
 
  ofstream file(detailFile);
 
     
 
  if(file){
   
    cout << "Saving detail file..."<< endl << flush;
 
    // line with "#" as first character are comments
 
    file << "###### Stop" << endl;
 
    file << stop << endl;
 
       
 
    file << "###### Init" << endl;
 
    file << init << endl;
 
	   
 
    file << "###### Number of iterations " << endl;
 
    file << swapIter[0] << endl;		
 
	       
 
    file << "###### Extraction feature reduction " << endl;
 
    // if (calcDim)
 
    file << calcDim << endl;
 
    // if (value)
 
    file << "###### selection feature reduction " << endl;
   
    file << value << endl;
   
					   
   
    file << "###### InitCenters() time " << endl;
   
    file << timeIter[0] << endl;		
   
					       
   
    file << "###### Swap in each iteration - one per line" << endl;
   
    for(i = 1 ; i < swapIter[0]+1 ; i++)
     
      file << swapIter[i] << endl;
   
										       
   
    file << "###### Time in each iteration - one per line" << endl;
   
    for(i = 1 ; i < swapIter[0]+1 ; i++)
     
      file << timeIter[i] << endl;
   
															       
   
    file << "###### Distance computed in each iteration - one per line" << endl;
   
    for(i = 1 ; i < swapIter[0]+1 ; i++)
     
      file << numExamples*calcDistIter[i] << endl;
   
  }
  file << "###### Dimension reduced used" << endl;
  file << dimReduced << endl;		
     
	       
     
     
  file.close();
     
  return TRUE;
     
}

/**********************************************************************

** printMsg

**********************************************************************/	

VOID	Kmeans::printMsg(CHAR* str,INT level){
  
  if(verbLevel>=level)
   
    cout << str << flush;
 
}

/**********************************************************************
 ** initCenters
 **********************************************************************/

INT	Kmeans::initCenters(){
  
 
 
  INT i, j, k;//, m;
  INT extra, avg, used;
  //CHAR str[80];
     
  if((numClusters > numExamples) || (numClusters == 0)){
    cout << "Error: wrong number of cluster requested." << endl << flush;
    exit(0);
  }
     
  // Choose cluster centers from points.
  // Must be chosen different numClusters
 							    
     
  //initialize random seed
  SRAND(time(NULL));						
     
     
  heap ClustQueue(numExamples);
  INT_VECTOR initCenter(numClusters);
	 
  for(i = 0 ; i < numExamples ; i++){
    ClustQueue.add(rand(),i);
  }
					     
  for(i = 0 ; i < numClusters ; i++){
    j = ClustQueue.remove(0);
    center.push_back(point[j]);
    initCenter[i] = j;
    //sprintf(str,"Initial center (%d) = %d\n",i,j);		
    //printMsg(str,DETAILED_MSGS);
  }
										 
  if (calcDim){//calculates tmpPoint for feature extraction
    //calcDim representa a dimensao final desejada para o vetor
		dimReduced = calcDim;
    avg = (INT) (dim / calcDim); // parte inteira, representa quantos elementos considerar na media
    extra = dim % calcDim;       // resto da divisao, a ser distribuido no inicio
    REAL_VECTOR rvtmp(calcDim);
   
    for(i = 0 ; i < numExamples ; i++ ){
      used  = extra; // inicializa o restinho a ser distribuido
      for(j = 0 ; j < calcDim ; j++){
				rvtmp[j] = 0;
				INT idx = avg * j + (extra - used); // calcula o index base da soma
				for(k = 0 ; k < avg ; k++){ // soma
					rvtmp[j] += point[i][idx + k];
				}
				// soma extra ?
				if(used){ 
					rvtmp[j] += point[i][idx + avg];
					rvtmp[j] = rvtmp[j] / (avg + 1.0);
					used--;
				}
				else 
					rvtmp[j] = rvtmp[j] / (REAL_NUMBER) avg;
      }
      tmpPoint.push_back(rvtmp);
    }

    for (i = 0; i < numClusters ; i++)
			tmpCenter.push_back(tmpPoint[initCenter[i]]);
  }
  if(value){ // initialize using feature selection
												 
    dimReduced = 0; // save for statistics 
    for (i = 0 ; i < dim ; i++){
      INT k = 0;
      for (j = 0 ; j < numExamples ; j++)
				if (ABS(point[j][i]) > 0.0001)
					k++;
      if(k >= value){
				chosenDim.push_back(i);
				dimReduced++;
			}
    }
		// copy vectores
		REAL_VECTOR rvtmp(chosenDim.size(),0);
		for(i = 0 ; i < numExamples ; i++){
			for(j = 0 ; j < chosenDim.size() ; j++){
				rvtmp[j] = point[i][chosenDim[j]];
			}
			tmpPoint.push_back(rvtmp);
		}

    for (i = 0; i < numClusters ; i++)
			tmpCenter.push_back(tmpPoint[initCenter[i]]);
  }

	for(i = 0 ; i < numExamples ; i++)
		membership.push_back(-1);	  

	/*															 
  switch(init){
  case 0: //no initialization at all
    for(i = 0 ; i < numExamples ; i++)
      membership.push_back(-1);	  
    break;
										   
  case 1: //random initialization without taking care to classes 
    for(i = 0 ; i < numExamples ; i++)
      membership.push_back(RAND(numClusters));
    break;
										   
  case 2: //random initialization taking care to classes 
    for(i = 0 ; i < numExamples ; i++){
      m=RAND(numClusters);
      while(target[m]!=target[i])
	m=RAND(numClusters);
      membership.push_back(m);
    }
    break;
  }
	*/							 
																	 
										 
  // initializing old centers matrix
  REAL_VECTOR old(dim,0);
										   
  for(i = 0 ; i < numClusters ; i++){
    numPointsInCluster.push_back(0);
    offsetMembership.push_back(-1);
    centerChanged.push_back(TRUE);
    REAL_VECTOR vtmp(numExamples,0);
    distance.push_back(vtmp);
  }
										   
  return TRUE;
																						 
										   
}

/**********************************************************************
 ** initCenters random
 **********************************************************************/

INT	Kmeans::initCentersRandom(){

  INT i, j;
  //CHAR str[80];
      
  if((numClusters > numExamples) || (numClusters == 0)){ 
    cout << "Error: wrong number of cluster requested." << endl << flush;
    exit(0);
  }
							  
//initialize random seed
  SRAND(time(NULL));						
          
  heap ClustQueue(numExamples);
  INT_VECTOR initCenter(numClusters);
	 
  for(i = 0 ; i < numExamples ; i++){
    ClustQueue.add(rand(),i);
		membership.push_back(-1);
		numPointsInCluster.push_back(0);
  }
					     
  for(i = 0 ; i < numClusters ; i++){
    j = ClustQueue.remove(0);
    center.push_back(point[j]);
    membership[i] = j;
		numPointsInCluster[i]=1;
    //sprintf(str,"Initial center (%d) = %d\n",i,j);		
    //printMsg(str,DETAILED_MSGS);
  }

	REAL_VECTOR rvtmp(dim,0);
  for(i = numClusters ; i < numExamples ; i++){
    center.push_back(rvtmp);
    membership[i] = -1;
		numPointsInCluster[i] = 0;
    //sprintf(str,"Initial center (%d) = %d\n",i,j);		
    //printMsg(str,DETAILED_MSGS);
  }
	
  return TRUE;
																												 
																												 
																												 
}

/**********************************************************************

** isSameVector

**********************************************************************/

INT Kmeans::isSameVector(REAL_VECTOR v1, REAL_VECTOR v2){
  
 
 
  INT same = TRUE;
 
  for(INT i = 0 ; i < v1.size() ; i++){
    if(v1[i] != v2[i]){ // ABS(v1[i] - v2[i]) > 0.0000001) -> trocar !
      same = FALSE;
      break;
    }
   
  }
 
  return same;	
 
}

/**********************************************************************

** calcDist

**********************************************************************/

REAL_NUMBER	Kmeans::calcDist(REAL_VECTOR& v1, REAL_VECTOR& v2){
  
 
 
  REAL_NUMBER tmp = 0;
 
   
 
  for(INT i = 0 ; i < v1.size() ; i++)
    //tmp += ABS(v1[i]-v2[i]);	
    tmp += (v1[i]-v2[i])*(v1[i]-v2[i]);	
 
					 
 
  return tmp;
 
}

/**********************************************************************

** calcPartialDist

**********************************************************************/

REAL_NUMBER	Kmeans::calcPartialDist(REAL_VECTOR& v1, REAL_VECTOR& v2){
  
  REAL_NUMBER tmp = 0;
  INT j;
 
  for(INT i = 0 ; i < chosenDim.size() ; i++){
    j = chosenDim[i]; 
    tmp += (v1[j]-v2[j])*(v1[j]-v2[j]);	
  }				
 
  return tmp;
 
}

















































